Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.
Example 1:
Input: nums = [1,0,1,1,0] Output: 4 Explanation: Flip the first zero will get the maximum number of consecutive 1s. After flipping, the maximum number of consecutive 1s is 4.
Example 2:
Input: nums = [1,0,1,1,0,1] Output: 4
Constraints:
1 <= nums.length <= 105nums[i]is either0or1.
Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?
Average Rating: 4.00 (8 votes)
Solution
Intuition
First, let's understand our problem.
"Given a binary array, find the maximum number of consecutive 1s in this array..."
Okay makes sense so far.
"...if you can flip at most one 0."
Huh? What does that even mean?
Let's translate that into something more concrete. We can rephrase "if you can flip at most one 0" into "allowing at most one 0 within an otherwise consecutive run of 1s". These statements are equal because if we had one 0 in our consecutive array, we could flip it to satisfy our condition. Note, we're not actually going to flip the 0 which will make our approach simpler.
So our new problem statement is:
"Given a binary array, find the maximum number of consecutive 1s in this array, allowing at most one 0 within an otherwise consecutive run of 1s"
Approach 1: Brute Force
Algorithm
Let's start simple and work our way up.
A brute force solution usually involves trying to check every single possibility. It'll look something like this:
- Check every possible consecutive sequence
- Count how many 0's are in each sequence
- If our sequence has one or fewer 0's, check if that's the longest consecutive sequence of 1's.
Interview Tip: Often times the interviewer doesn't need to see you code the brute force solution. State the brute force approach out loud and discuss his/her expectations. Either way, communicating proactively will give you major bonus points.
Complexity Analysis
Let n be equal to the length of the input nums array.
-
Time complexity : O(n2). The nested
forloops turn our approach into a quadratic solution because for every index, we have to check every other index in the array. -
Space complexity : O(1). We are using 4 variables: left, right, numZeroes, longestSequence. The number of variables are constant and do not change based on the size of the input.
Approach 2: Sliding Window
Intuition
The naive approach works but our interviewer is not convinced. Let's see how we can optimize the code we just wrote.
The brute force solution had a time complexity of O(n2). What was the bottleneck? Checking every single consecutive sequence. Intuitively, we know we're doing repeated work because sequences overlap. We are checking consecutive sequence blindly. We need to establish some rules on how to move our sequence forward.
- If our sequence is valid, let's continue expanding our sequence (because our goal is to get the largest sequence possible).
- If our sequence is invalid, let's stop expanding and contract our sequence (because an invalid sequence will never count towards our largest sequence).
The pattern that comes to mind for expanding/contracting sequences is the sliding window. Let's define valid and invalid states.
- Valid State = one or fewer 0's in our current sequence
- Invalid State = two 0's in our current sequence
Algorithm
Great. How do we apply all this to the sliding window?
Let's use left and right pointers to keep track of the current sequence a.k.a. our window. Let's expand our window by moving the right pointer forward until we reach a point where we have more than one 0 in our window. When we reach this invalid state, let's contract our window by moving the left pointer forward until we have a valid window again. By expanding and contracting our window from valid and invalid states, we are able to traverse the array efficiently without repeated overlapping work.
Now we can break this approach down into a few actionable steps:
While our window is in bounds of the array...
- Add the rightmost element to our window
- Check if our window is invalid. If so, contract the window until valid.
- Update our the longest sequence we've seen so far
- Continue to expand our window
This will look like this:
Complexity Analysis
Let n be equal to the length of the input nums array.
-
Time complexity : O(n). Since both the pointers only move forward, each of the left and right pointer traverse a maximum of n steps. Therefore, the timecomplexity is O(n).
-
Space complexity : O(1). Same as the previous approach. We don't store anything other than variables. Thus, the space we use is constant because it is not correlated to the length of the input array.
January 3, 2021 8:04 AM
Simpler, one pointer: track two sets of ones, current set and previous set, resetting previous to 0 if 2 consecutive 0s are encountered. Add 1 if at least one 0 is encountered:
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0;
int curr = 0, prev = 0, seenZero = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
seenZero = 1;
prev = curr;
curr = 0;
} else {
curr++;
}
max = Math.max(max, curr + prev + seenZero);
}
return max;
}
}
Last Edit: January 2, 2021 1:10 PM
Follow up infinite stream - Maintain the 'left', 'right' and 'last seen zero'. As soon as one encounters another 0 in stream, record the maxLength; make leftIndex = zeroIndex + 1, and set zeroIndex = right = curIndex. Again continue processing the stream.
does sliding window concept work with infinite stream of input nums as well? What is the reasoning if yes/no
Very simple solution is to track if you have seen a zero, the count of the current run of ones, the count of the last run of ones, and the max length run you've seen.
When you see a one, increment the current run count.
When you see a zero, note that you've seen one (if you don't see one, the max consecutive ones is length of the input array), then update max total seen to be max of current max total seen and the sum of the previous run, current run, plus one to "flip" the zero between them. Then set the previous run counter to the current run counter, and reset the current run counter back to 0.
When you reach the end, if you haven't seen a zero, you can return the maximum consecutive ones to be the input length, else, it's the max of max total run seen, and the sum of previous, current, plus one, same as in the iteration.
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
seenZero = False
currOnes = 0
prevOnes = 0
maxRun = 0
for num in nums:
if num == 1:
currOnes += 1
else:
seenZero = True
maxRun = max(maxRun, prevOnes + 1 + currOnes)
prevOnes = currOnes
currOnes = 0
return len(nums) if not seenZero else max(maxRun, prevOnes + 1 + currOnes)
Why my solution below is still consuming 2ms whenever I run this piece of code, I feel like code below is exactly same as the approach here:
public int findMaxConsecutiveOnes(int[] nums) {
int slow = 0;
int fast = 0;
int max = 0; // [1,0,1,1,0]
int index = 0;
boolean isFlipped = false;
while(fast < nums.length){
if(nums[fast]==1){
fast++;
}else if(!isFlipped){
index = fast;
fast++;
isFlipped = true;
}else{
isFlipped = false;
slow = index+1;
fast = slow;
}
max = Math.max(max,fast-slow);
}
return max;
}
Very simple solution with 1 pointer.
int findMaxConsecutiveOnes(vector& nums) {
bool skipOne = true;
int skipIdx = 0;
int maxLen = 0;
int serieLen = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 1 || skipOne) {
serieLen++;
if (nums[i] == 0) {
skipOne = false;
skipIdx = i;
}
} else {
//num == 0 and a 0 was already skipped.
// flush the counter and readjust the current serieLen
maxLen = max(maxLen, serieLen);
serieLen = i - skipIdx;
skipIdx = i;
}
}
maxLen = max(maxLen, serieLen);
return maxLen;Different version using sliding window :
class Solution:
def findMaxConsecutiveOnes(self, nums ) :
if not nums:
return
start = 0
res = float('-inf')
d = {}
for end in range(len(nums)):
if nums[end] == 1 :
pass
else :
if 0 not in d :
d[0] = end
else :
start = d.get(0) + 1
d[0] = end
res = max(res, end - start + 1)
return resLittle more optimized solution with two pointers than approach 2. This solution will have better runtime when numbers of zeros are less as compared to ones and are distributed. This solution is written in Java Language.
Runtime = O(n) and Space = O(1)
public int findMaxConsecutiveOnes(int[] nums) {
int ans = 0; // it will hold the max length of valid sequence
int start = 0; // it will hold the start index of valid sequence
int zeroAt = -1; // store the last '0' encountered position, -1 means not encountered
// iterate over numbers and noting indexes of '0' and
// start index of valid sequences
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
if (zeroAt > -1) {
//if we have encountered a '0' already
// try to update the result and start position
ans = Math.max(ans, i - start);
start = zeroAt+1;
}
zeroAt = i; // always update new '0' position
}
}
// finally check with last valid sequence, i.e., if nums[length-1] == 1
ans = Math.max(ans, nums.length - start);
return ans;
}
Approach №2: on the second slide of algorithm visualization longestSequence should be equal to 2, not to 1, as we can swap first zero and get 2 consecutive 1s. We just need to start with longestSequence equals to 1 on the first slide.
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 05/30/2021 20:07 | Accepted | 36 ms | 36 MB | cpp |
xxxxxxxxxxclass Solution {public: // Two pointer approach int findMaxConsecutiveOnes(vector<int>& nums) { int ones = 0; int ones_and_zero = 0; int res = 0; for (int num : nums) { if (num == 1) { ++ones; ++ones_and_zero; } else { ones_and_zero = ones + 1; ones = 0; } res = max(res, ones_and_zero); } return res; }};